//
// Created by PC on 2024/11/1.
// https://hydro.ac/d/teddycode/p/GESP5010
// 4pass 6wrong
/*
 * 挑战怪物
时间限制：1.0 s
内存限制：512.0 MB
3.2.1 题面描述
小杨正在和一个怪物战斗，怪物的血量为h，只有当怪物的血量恰好为0 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式：
物理攻击。假设当前为小杨第i次使用物理攻击，则会对怪物造成2^(i-1) 点伤害。
魔法攻击。小杨选择任意一个质数 x（ x不能超过怪物当前血量），对怪物造成 x点伤害。由于小杨并不擅长魔
法，他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。
3.2.2 输入格式
第一行包含一个正整数t ，代表测试用例组数。
接下来是t 组测试用例。对于每组测试用例，第一行包含一个正整数h ，代表怪物血量。
3.2.3 输出格式
对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物，
输出 -1。
3.2.4

样例1:
 input:
3
6
188
9999
output:
2
4
-1
对于第一组测试用例，一种可能的最优方案为，小杨先对怪物使用魔法攻击，选择质数 5造成 5点伤害，之后对怪
物使用第 1次物理攻击，造成2^(1-1) 点伤害，怪物血量恰好为0 ，小杨成功击败怪物。
子任务编号 数据点占比
        t   	h
1 	20%	<=5 	<=10
2 	20%	<=10	<=100
3 	60%	<=10	<=10^5
对于全部数据，保证有 t=[1,10],h=[1,10^5]。
 * */
//


#include <iostream>
#include <vector>

using namespace std;


int searchLastSmall(vector<int> &vv, int x)
{
    // 二分法查找
    // 查找最后一个小于等于h的数
    int m; // 二分查找中点位置
    int t = -1; // 记录h在primes的位置
    int l = 0, r = vv.size() - 1;
    while (l <= r)
    {
        m = l + (r - l) / 2;
        if (vv[m] <= x)
        {
            t = m;
            l = m + 1;
        } else
            r = m - 1;
    }
//            cout<<primes[t]<<endl;
    return t;
}

// 查找任意相等相同元素的索引位置,没有就返回-1
int searchEqual(vector<int> &vv, int target)
{
    int l = 0, r = vv.size() - 1, m;
    if (target < vv[l] || target > vv[r])
        return -1;
    while (l <= r)
    {
        m = r + (l - r) / 2;
        if (target < vv[m])
            r = m - 1;
        else if (target > vv[m])
            l = m + 1;
        else
            return m;
    }
    return -1;

}

int main()
{
    vector<int> attack = {0}; // 普通攻击
    vector<int> primes; // 魔法攻击
    int n = 100000;
    // attack保存前缀和, 数组内容是0 1 3 7 15 31 63 127
    for (int i = 1, j = 0; i <= n; i *= 2, j++)
        attack.push_back(i + attack[j]);
    // primes保存质数 2 3 5 7 11 13 17 19 23 29 31 37
    bool isp[n + 1] = {0};
    for (int i = 2; i <= n; ++i)
        isp[i] = 1;
    for (int i = 2; i * i <= n; ++i)
    {
        if (isp[i])
        {
            for (int j = 2 * i; j <= n; j += i)
                isp[j] = 0;
        }
    }
    for (int i = 0; i <= n; ++i)
    {
        if (isp[i])
            primes.push_back(i);
    }
    int t;
    cin >> t;
    while (t--)
    {
        int h;
        cin >> h;
        // h是奇数结果是质 or 1+n
        if (h % 2 != 0)
        {
            int ret = searchLastSmall(primes, h);
            // 恰好等于质数
            if (primes[ret] == h)
                cout << 1;  // 质数攻击一次就打败了
                // 不是质数 就是1+n
            else
            {
                ret = searchLastSmall(attack, h);
                if (attack[ret] == h)
                    cout << ret<<endl;
                else
                    cout << -1<<endl;
            }
        }
            // h是偶数结果就是质+2^n
        else
        {
            // 先找到比h小的最大质数的位置
            int i = searchLastSmall(primes, h);
            int ret = -1;
            for (int j = i; j >= 0; --j)
            {
                int left_h = h - primes[j]; // 质数攻击后剩下的血量
                ret = searchEqual(attack, left_h);
                // 在普通攻击里没找到, 说明无法打败,向下继续换一个更小的质数
                if (ret == -1)
                    continue;
                else
                {
                    ret += 1; // 攻击数=普通攻击数(ret)+1(质数攻击数)
                    break;
                }
            }
            cout<<ret<<endl;
        }

    }
    return 0;
}